import java.util.*;


/**
 * A class that contains a group of sorting algorithms.
 * The input to the sorting algorithms is assumed to be
 * an array of integers.
 * 
 * @author Donald Chinn
 * @version January 10, 2012
 */
public class Sort {

    // Constructor for objects of class Sort
    public Sort() {
    }


    /**
     * Given an array of integers, sort the array
     * (ascending order) using mergesort.
     * @param data  an array of integers
     */
    public static void mergesort (int[] data) {
        mergesortRecursive (data, 0, data.length - 1);
    }
    
    /**
     * The recursive part of mergesort.
     * Given an array of integers (data), a low index, and high index,
     * sort the subarray data[low..high] (ascending order) using mergesort.
     * @param data  an array of integers
     * @param low   low index
     * @param high  high index
     */
    private static void mergesortRecursive (int[] data, int low, int high) {
        if (low < high) {
            mergesortRecursive (data,
                                low,
                                (low + high) / 2 );
            mergesortRecursive (data,
                                (low + high) / 2 + 1,
                                high );
            merge (data, low, high);
        }
    }
    

    /**
     * Given an array of integers (data), a low index, and a high index,
     * sort the subarray data[low..high].  This method assumes that each of the
     * 2 subarrays,
     *   data[low .. (low + high) / 2] and  data[(low + high) / 2 + 1 .. high]
     * are sorted.
     */
    private static void merge (int[] data, int low, int high) {
    
        if (high > low) {
            int i = low;				// index into first subarray
            int endFirstSubarray = (low + high) / 2;
            int j = (low + high) / 2 + 1;	// index into the second subarray

            int[] outputArray = new int[high - low + 1];
            int k = 0;				// index into output array

            // perform merge on the two subarrays
            while ( (i <= endFirstSubarray) && (j <= high) ) {
                if (data[i] <= data[j]) {
                    outputArray[k] = data[i];
                    i++;
                } else {
                    outputArray[k] = data[j];
                    j++;
                }
                k++;
            }

            // copy the rest of the uncopied subarray
            if ( i == endFirstSubarray + 1 ) {
                while (j <= high) {
                    outputArray[k] = data[j];
                    k++;
                    j++;
                }
            } else {
                while (i <= endFirstSubarray) {
                    outputArray[k] = data[i];
                    k++;
                    i++;
                }
            }

            // copy the sorted array back into the input array
            for (k = 0, i = low; i <= high; k++, i++) {
                data[i] = outputArray[k];
            }
        }
    }
    

    /**
     * Given an array of integers, sort the array
     * (ascending order) using heapsort.
     * @param data  an array of integers
     */
    public static void heapsort(int[] data) {
    	/*
    	// we need data to be comparable!
    	Integer[] intArray = new Integer[data.length];
    	for(int i = 0; i < data.length; i++) {
    		intArray[i] = Integer.valueOf(data[i]);
    	}
    	// we need a binary heap!
    	BinaryHeap bheap = BinaryHeap.buildHeap(intArray);
    
    	// We have a binary heap that has the integers in data[]! We now have to 
    	// get the values in the heap (in sorted order) and place it back into data[]
    	for(int j = 0; j < data.length; j++) {
    		try {
    			// we need to convert the Integer object back into an int object
				data[j] = ((Integer) bheap.deleteMin()).intValue();
			} catch (EmptyHeapException e) {
			}
    	}
    	*/
    	
    	// create a binary heap
    	BinaryHeap bheap = new BinaryHeap(data.length);
    	// fill the binary heap with integers from data
    	for(int i = 0; i < data.length; i++) {
    		// we need to convert int to Integer (Integer implements Comparable)
    		bheap.insert(Integer.valueOf(data[i]));
    	}
    	
    	// We have a binary heap that has the integers in data[]! We now have to 
    	// get the values in the heap (in sorted order) and place it back into data[]
    	for(int j = 0; j < data.length; j++) {
    		try {
    			// we need to convert the Integer object back into an int object
				data[j] = ((Integer) bheap.deleteMin()).intValue();
			} catch (EmptyHeapException e) {
			}
    	}
    	
    }


    /**
     * Given an integer size, produce an array of size random integers.
     * The integers of the array are between 0 and size (inclusive) with
     * random uniform distribution.
     * @param size  the number of elements in the returned array
     * @return      an array of integers
     */
    public static int[] getRandomArrayOfIntegers(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = (int) ((size + 1) * Math.random());
        }
        return data;
    }
    

    /**
     * Given an integer size, produce an array of size random integers.
     * The integers of the output array are between 0 and size-1 with
     * exactly one of each in the array.  Each permutation is generated
     * with random uniform distribution.
     * @param size  the number of elements in the returned array
     * @return      an array of integers
     */
    public static int[] getRandomPermutationOfIntegers(int size) {
        int[] data = new int[size];
        for (int i = 0; i < size; i++) {
            data[i] = i;
        }
        // shuffle the array
        for (int i = 0; i < size; i++) {
            int temp;
            int swap = i + (int) ((size - i) * Math.random());
            temp = data[i];
            data[i] = data[swap];
            data[swap] = temp;
        }
        return data;
    }


    /**
     * Perform checks to see if mergesort has a bug.
     */
    private static void testCorrectnessOfMergesort() {
        int[] data = getRandomPermutationOfIntegers(100);
        
        System.out.println("Testing correctness of mergesort ...");
        for (int i = 0; i < data.length; i++) {
            System.out.println("data[" + i + "] = " + data[i]);
        }
        
        int k = 100;
        mergesort(data);
        
        // verify that data[i] = i
        for (int i = 0; i < data.length; i++) {
            if (data[i] != i) {
                System.out.println ("Error!  data[" + i + "] = " + data[i] + ".");
            }
        }
    }
    

    /**
     * Perform checks to see if heapsort has a bug.
     */
    private static void testCorrectnessOfHeapsort() {
        int[] data = getRandomPermutationOfIntegers(100);
        
        System.out.println("Testing correctness of heapsort ...");
        for (int i = 0; i < data.length; i++) {
            System.out.println("data[" + i + "] = " + data[i]);
        }
        
        int k = 100;
        heapsort(data);
        
        // verify that data[i] = i
        for (int i = 0; i < data.length; i++) {
            if (data[i] != i) {
                System.out.println ("Error!  data[" + i + "] = " + data[i] + ".");
            }
        }
    }
   

    /**
     * Perform timing experiments.
     */
    private static void testTimingOfMergesort () {
        // timer variables
        long totalTime = 0;
        long startTime = 0;
        long finishTime = 0;

        int n = 100000;    // n = size of the array
        int[] data = getRandomArrayOfIntegers(n);

        // start the timer
        Date startDate = new Date();
        startTime = startDate.getTime();

        mergesort(data);

        // stop the timer
        Date finishDate = new Date();
        finishTime = finishDate.getTime();
        totalTime += (finishTime - startTime);
        
        System.out.println("** Results for mergesort:");
        System.out.println("    " + "n = " + n);
        System.out.println("    " + "Time: " + totalTime + " ms.");
    }


    /**
     * Perform timing experiments.
     */
    private static void testTimingOfHeapsort () {
        // timer variables
        long totalTime = 0;
        long startTime = 0;
        long finishTime = 0;

        int n = 3200000;    // n = size of the array
        int[] data = getRandomArrayOfIntegers(n);

        // start the timer
        Date startDate = new Date();
        startTime = startDate.getTime();

        heapsort(data);

        // stop the timer
        Date finishDate = new Date();
        finishTime = finishDate.getTime();
        totalTime += (finishTime - startTime);
        
        System.out.println("** Results for heapsort:");
        System.out.println("    " + "n = " + n);
        System.out.println("    " + "Time: " + totalTime + " ms.");
    }
    
    /**
     * code to test the sorting algorithms
     */
    public static void main (String[] argv) {
        testCorrectnessOfMergesort();
        testTimingOfMergesort();

        testCorrectnessOfHeapsort();
        testTimingOfHeapsort();
    }
}
